/*
 * sum of elements [i;j]
 */
int rsq(int i, int j);

/*
 * add 'd' to 'k'th element
 */
void update(int k, int d);

/*
 * 1 naive
 *   rsq    - O(n)
 *   update - O(1)
 *
 * 2 pre-calculations
 *  b[k] = \sum_{i=0}^k a[i]
 *  rsq(i,j) = b[j] - b[i-1]
 *   rsq    - O(1)
 *   update - O(n)
 * 3 fenwick tree
 *   rsq    - O(log(n))
 *   update - O(log(n))
 */
/*
 * given a[0;n]
 *   let b[0;n]
 *       b[k] = \sum_{i=f(k)}^k a[i]
 *   f(k) := k & (k+1) #bitwise AND
 *       # k  : ... 01 ... 1
 *       # k+1: ... 10 ... 0
 */

/*  k : f(k),k
 *  0 :    0,0
 *  1 :    0,1
 *  2 :    2,2
 *  3 :    0,3
 *  4 :    4,4
 *  5 :    4,5
 *  6 :    6,6
 *  7 :    0,7
 *  8 :    8,8
 *  9 :    8,9
 * 10 :    8,10
 */

/*
 * rsq(i,j) = rsq(j) - rsq(i-1)
 *             \
 *              `sum(a[0;j])
 *
 * rsq(k) = b[k] + b[f(k)-1] + b[f(f(k)-1)-1] + b[f(f(...f(k)-1)...)-1)-1] =
 *  = b[k_0] + b[k_1] + b[k_2] + ... + b[k_m]
 *
 * k_{i+1} = f(k_i) - 1 #next 'k'
 * k_0 = k
 * f(k) <= k
 * f(k) - 1 < k
 *
 * b[k_0] + b[k_1] + ... + b[k_m] = \sum_{i=f(k_0)}^{k_0} a[i] + \sum_{i=f(k_1)}^{k_1} a[i] + ... + \sum_{i=f(k_m)}^{k_m} a[i] =
 *  = \sum_{i=f(k_0)}^{k_0} a[i] + \sum_{i=f(k_1)}^{f(k_0)-1} a[i] + ... + \sum_{i=f(k_m)}^{f(k_m)-1} a[i] =
 *  = \sum_{i=f(k_m)}^{k_0} a[i] = \sum_{i=0}^{k_0} a[i]
 *
 * rsq(14) = b[14] + b[13] + b[11] + b[7] = a[14] + sum(a[12;13]) + sum(a[8;11]) + sum(a[0;7]) = sum(a[0;14])
 */

/*
 * update(k,d)
 *
 *  f(j) <= k <= j
 *
 *  {k_0 = k
 *  {k_{i+1} = k_i | (k_i + 1)
 *
 *  k_{m+1} = k_m | (k_m + 1) > n - 1 #rightmost 0 bit becomes 1
 *
 * k = k_0 < k_1 < k_2 < ... < k_m
 * f(k_m) <= ... <= f(k_1) <= f(k_0) <=  k = k_0  < k_1 < k_2 < ... < k_m
 *
 * f(j) <= k <= j
 * j    X01..1
 * k    X0????
 * f(j) X00..0
 */

/* How to build the tree:
 *
 * init():
 * 	zero out b
 * 	for (i=0;i<n;++i)
 * 		update(fTree,i,a[i])
 * O(n*log(n))
 */
/*
   vim:ft=c :
 */
